from typing import List


# 322. 零钱兑换
# 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
# 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
# 你可以认为每种硬币的数量是无限的。
def coinChange(coins: List[int], amount: int) -> int:
    dp = [-1] * (amount + 1)
    dp[0] = 0
    # 遍历每一种情况
    for i in range(1, amount + 1):
        # 遍历每一个硬币
        for coin in coins:
            if coin <= i and dp[i - coin] != -1:
                compare_count = dp[i - coin] + 1
                dp[i] = min(compare_count, dp[i]) if dp[i] != -1 else compare_count
    return dp[amount]


coins_1 = [1, 2, 5]
amount_1 = 11
result = coinChange(coins_1, amount_1)
print(f"result:{result}")

coins_1 = [2]
amount_1 = 3
result = coinChange(coins_1, amount_1)
print(f"result:{result}")

coins_1 = [1]
amount_1 = 0
result = coinChange(coins_1, amount_1)
print(f"result:{result}")
